The vehicle routing problem is a combinational optimization problem that seeks to provide an optimal vehicle routing plan for servicing customers with a fleet of vehicles. Many distribution and transportation systems use the vehicle routing problem as an important planning component, including banking systems, postal services, school bus routing, and security patrol services. A standard two-part objective of the vehicle routing problem is to minimize the number of routes or vehicles and the total travel time of the vehicles.
The vehicle routing problem with time windows (VRPTW) is an extension of the vehicle routing problem that requires customers to be serviced within a time window. VRPTW involves a number of customers with known demands and a fleet of identical vehicles with known capacities. The problem includes finding a vehicle routing plan including a set of vehicle routes originating and terminating at a central depot. The vehicle routing plan must service each customer exactly once and the vehicle routes cannot violate the known capacity constraints of the vehicles.
Military systems may use VRPTW to supply troops in the field. Supply operations involve varying levels of autonomy and mission complexity and may service the troops using unmanned air vehicles, unmanned ground vehicles (UGV), and unmanned underwater vehicles. One example of a UGV is the multi-function utility logistics and equipment (MULE) vehicle, which is a 2.5 ton vehicle that can transport equipment and supplies to support dismounted maneuver forces. The MULE can efficiently perform supply operations at the battalion level over geographic areas as large 100 square kilometers. Such operations may be divided into smaller scale missions to support troops at the company and platoon level.